#include <cstdio>
#include <cstdlib>
#include <sys/cdefs.h>
//
// Created by REEJI2219 on 2024-08-12.
//
class Node {
public:
    int a;//a系数
    int n;//b为指数
    Node *next;
    Node() {
        a=0;
        n=0;
        next=nullptr;
    }
    ~Node() {
        delete next;
    }
};
class List {
private:
    Node *head;
public:
    List() {
        head = nullptr;
    }
    bool add(Node *node) {
        if(!head) {
            head = node;
            return true;
        }
        if(head->n==node->n) {
            head->a=head->a+node->a;
            if(head->a==0) {
                Node *tmp=head;
                head=head->next;
                delete tmp;
            }
            return true;
        }
        //当前节点
        Node *current = head;
        //上一个节点，在出现系数为0是，方便删除
        Node *preNode = nullptr;
        while (current->next) {
            //中间节点处理
            if(current->n==node->n) {
                current->a=current->a+node->a;
                //系数为0,删除该节点
                if(current->a==0) {
                    preNode->next=current->next;
                    free(current);
                }
                return true;
            }
            preNode=current;
            current= current->next;
        }
        //尾巴节点处理
        if(current->n==node->n) {
            current->a=current->a+node->n;
            //系数为0,删除该节点
            if(current->a==0) {
                preNode->next=nullptr;
                delete current;
            }
            return true;
        }
        //没找到，新加就行了
        current->next=node;
    }
    bool add(int a,int n) {
        if(!head) {
            head = new Node;
            head->a=a;
            head->n=n;
            return true;
        }
        //n < 头结点，添加到前面
        if(n<head->n) {
            Node *tmp = new Node();
            tmp->n=n;
            tmp->a=a;
            tmp->next=head;
            head=tmp;
            return true;
        }
        //等于同节点，合并到头节点
        if(head->n==n) {
            head->a=head->a+a;
            if(head->a==0) {
                Node *tmp=head;
                head=head->next;
                delete tmp;
            }
            return true;
        }
        //当前节点
        Node *current = head;
        //上一个节点，在出现系数为0是，方便删除
        Node *preNode = nullptr;
        while (current->next) {
            //中间节点处理
            if(current->n==n) {
                current->a=current->a+a;
                //系数为0,删除该节点
                if(current->a==0) {
                    preNode->next=current->next;
                    free(current);
                }
                return true;
            }
            //与下个节点进行比较
            if(n<current->next->n) {
                Node *tmp = new Node();
                tmp->n=n;
                tmp->a=a;
                tmp->next=current->next;
                current->next=tmp;
                return true;
            }
            preNode=current;
            current= current->next;
        }
        //尾巴节点处理
        if(current->n==n) {
            current->a=current->a+a;
            //系数为0,删除该节点
            if(current->a==0) {
                preNode->next=nullptr;
                delete current;
            }
            return true;
        }
        //没找到，新加就行了
        Node *next = new Node();
        next->a=a;
        next->n=n;
        current->next=next;
    }
    bool printList() {
        Node *current=head;
        printf("%dX^%d ",current->a,current->n);
        while (current->next) {
            current = current->next;
            printf("%dX^%d ",current->a,current->n);
        }
        printf("\n");
    }
    bool addOther(List *list) {
        Node *curredHead = this->head;
        Node *otherHead = list->head;
        Node *preHead = this->head;
        //头部节点
        while (curredHead && otherHead) {
            Node *tmpOther = otherHead;
            //other比当前小，插入到前面
            if(otherHead->n <curredHead->n) {
                otherHead = otherHead->next;
                if(curredHead==this->head) {
                    tmpOther->next=curredHead;
                    this->head = tmpOther;
                    preHead=this->head;
                    curredHead=preHead;
                }else {
                    tmpOther->next=curredHead;
                    preHead->next=tmpOther;
                    curredHead=preHead->next;
                }
                continue;
            }
            //相等，添加系数，当前后延
            if(otherHead->n == curredHead->n) {
                curredHead->a = curredHead->a+otherHead->a;
                otherHead = otherHead->next;
                //系数为0，删除当前节点
                if(curredHead->a==0) {
                    if(curredHead=this->head) {
                        this->head=this->head->next;
                        curredHead=this->head;
                        preHead=this->head;
                    }else {
                        preHead->next=curredHead->next;
                    }
                }
                continue;
            }
            if(otherHead->n > curredHead->n) {
                preHead = curredHead;
                curredHead=curredHead->next;
            }
        }
        while (otherHead) {
            curredHead->next=otherHead;
        }
    }
};

// int main() {
//     List *list = new List();
//     list->add(1,4);
//     list->add(2,2);
//     list->add(3,2);
//     list->printList();
//     List *list2 = new List();
//     list2->add(-2,1);
//     list2->add(-1,4);
//     list2->printList();
//     list->addOther(list2);
//     list->printList();
// }